DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2024.22

Evaluating Graph Queries Using Semantic Treewidth

Authors: Cristina Feier, Tomasz Gogacz, and Filip Murlak

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract

Unions of conjunctive two-way regular path queries (UC2RPQs) are a common abstraction of query languages for graph databases, much like unions of conjunctive queries (UCQs) in the relational case. As in the case of UCQs, their evaluation is NP-complete in combined complexity. Semantic tree-width, i.e. the minimal treewidth of equivalent queries, has been proposed as a candidate criterion to characterize fixed-parameter tractability of UC2RPQs. It was recently shown how to decide the semantic tree-width of a UC2RPQ, by constructing the best under-approximation of a given treewidth, in the form of a UC2RPQ of size doubly exponential in the size of the original query. This leads to an fpt algorithm for evaluating UC2RPQs of semantic TW k which runs in time doubly exponential in the size of the parameter, i.e. in the UC2RPQ. Here we describe a more efficient fpt algorithm for evaluating UC2RPQs of semantic treewidth k which runs in time singly exponential in the size of the parameter. We do this by a careful construction of a witness query which, while still being doubly exponential, can be represented as a Datalog program of bounded width and singly exponential size.

Cite as

Cristina Feier, Tomasz Gogacz, and Filip Murlak. Evaluating Graph Queries Using Semantic Treewidth. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feier_et_al:LIPIcs.ICDT.2024.22,
  author =	{Feier, Cristina and Gogacz, Tomasz and Murlak, Filip},
  title =	{{Evaluating Graph Queries Using Semantic Treewidth}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.22},
  URN =		{urn:nbn:de:0030-drops-198048},
  doi =		{10.4230/LIPIcs.ICDT.2024.22},
  annote =	{Keywords: conjunctive two-way regular path queries, fixed-parameter tractable evaluation, semantic treewidth, Datalog encoding, optimization}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2017.15

Entropy Bounds for Conjunctive Queries with Functional Dependencies

Authors: Tomasz Gogacz and Szymon Torunczyk

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract

We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive query Q applied to a database D satisfying given functional dependencies. We provide a characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by [Gottlob, Lee, Valiant and Valiant, J.ACM, 2012] is tight, and that a correspondence of [Chan and Yeung, ACM TOIT, 2002] is preserved in the presence of functional dependencies. However, tightness of a weaker upper bound provided by Gottlob et al., which would have immediate applications to evaluation of join queries ([Khamis, Ngo, and Suciu, PODS, 2016]) remains open. Our result shows that the problem of computing the worst-case size bound, in the general case, is closely related to difficult problems from information theory.

Cite as

Tomasz Gogacz and Szymon Torunczyk. Entropy Bounds for Conjunctive Queries with Functional Dependencies. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gogacz_et_al:LIPIcs.ICDT.2017.15,
  author =	{Gogacz, Tomasz and Torunczyk, Szymon},
  title =	{{Entropy Bounds for Conjunctive Queries with Functional Dependencies}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.15},
  URN =		{urn:nbn:de:0030-drops-70479},
  doi =		{10.4230/LIPIcs.ICDT.2017.15},
  annote =	{Keywords: database theory, conjunctive queries, size bounds, entropy, finite groups, entropy cone}
}

Search Results

Documents authored by Gogacz, Tomasz

Evaluating Graph Queries Using Semantic Treewidth

Abstract

Cite as

Entropy Bounds for Conjunctive Queries with Functional Dependencies

Abstract

Cite as

Thanks for your feedback!

Could not send message